package lb.test.core.alg;

import java.util.*;

public class MyBinaryTree {

    private static TreeNode createCompBinaryTree(LinkedList<String> list){
        TreeNode root = new TreeNode(list.get(0));
        List<TreeNode> nodes = new ArrayList<>();
        List<TreeNode> temp = new ArrayList<>();
        nodes.add(root);
        for (int i = 1; i < list.size();) {
            for (TreeNode node : nodes) {
                node.left = new TreeNode(list.get(i));
                temp.add(node.left);
                i++;
                if (i < list.size()) {
                    node.right = new TreeNode(list.get(i));
                    temp.add(node.right);
                }
                i++;
            }
            nodes.clear();
            nodes.addAll(temp);
            temp.clear();
        }
        return root;
    }


    public static void testTree() {
        String[] values = {"A", "B", "C", "D", "E", "F"};
        /**
         *        A
         *      /  \
         *     B    C
         *    /\   /
         *   D E  F
         */
        TreeNode treeNode = createCompBinaryTree(new LinkedList<>(Arrays.asList(values)));

        new PreorderTravers().travers(treeNode);
        new MidTravers().travers(treeNode);
        new BehindTravers().travers(treeNode);
        new LayerTravers().travers(treeNode);

        new PreorderNoRecTravers().travers(treeNode);
        new MidNoRecTravers().travers(treeNode);
        new BehindNoRecTravers().travers(treeNode);
        new LayerNoRecTravers().travers(treeNode);
    }

    public static class PreorderTravers extends BaseTravers {

        @Override
        protected void doTravers(TreeNode node) {
            if (node == null) {
                return;
            }
            visitNode(node);
            doTravers(node.left);
            doTravers(node.right);
        }
    }

    public static class MidTravers extends BaseTravers {

        @Override
        protected void doTravers(TreeNode node) {
            if (node == null) {
                return;
            }
            doTravers(node.left);
            visitNode(node);
            doTravers(node.right);
        }
    }
    public static class BehindTravers extends BaseTravers {

        @Override
        protected void doTravers(TreeNode node) {
            if (node == null) {
                return;
            }
            doTravers(node.left);
            doTravers(node.right);
            visitNode(node);
        }
    }

    public static class LayerTravers extends BaseTravers {

        @Override
        protected void doTravers(TreeNode node) {
            layerTrav(node);
        }

        private void layerTrav(TreeNode...nodes) {
            List<TreeNode> list = new ArrayList<>();
            for (TreeNode node : nodes) {
                visitNode(node);
                if (node.left != null) {
                    list.add(node.left);
                }
                if (node.right != null) {
                    list.add(node.right);
                }
            }
            if (list.size() > 0) {
                layerTrav(list.toArray(new TreeNode[0]));
            }
        }
    }
    //====================非递归实现========================
    public static class PreorderNoRecTravers extends BaseTravers {

        @Override
        protected void doTravers(TreeNode node) {
            Stack<TreeNode> stack = new Stack<>();
            stack.push(node);
            while (!stack.empty()) {
                TreeNode tn = stack.pop();
                visitNode(tn);
                if (tn.right != null) {
                    stack.push(tn.right);
                }
                if (tn.left != null) {
                    stack.push(tn.left);
                }
            }
        }
    }

    public static class MidNoRecTravers extends BaseTravers {

        @Override
        protected void doTravers(TreeNode node) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode tempNode = node;
            while (tempNode != null || !stack.empty()) {
                while (tempNode != null) {
                    stack.push(tempNode);
                    tempNode = tempNode.left;
                }
                if (!stack.isEmpty()) {
                    tempNode = stack.pop();
                    visitNode(tempNode);
                    tempNode = tempNode.right;
                }
            }
        }
    }
    public static class BehindNoRecTravers extends BaseTravers {

        @Override
        protected void doTravers(TreeNode node) {

            Stack<TreeNode> stack = new Stack<>();
            TreeNode tempNode = node;
            TreeNode lastNode = null;

            while (tempNode != null  || !stack.isEmpty()) {

                while (tempNode != null) {
                    stack.push(tempNode);
                    tempNode = tempNode.left;
                }

                if (!stack.isEmpty()) {
                    tempNode = stack.pop();
                    if (tempNode.right == null || tempNode.right == lastNode) {
                        visitNode(tempNode);
                        lastNode = tempNode;
                        tempNode = null;
                    } else {
                        stack.push(tempNode);
                        tempNode = tempNode.right;
                    }
                }
            }

        }
    }

    public static class LayerNoRecTravers extends BaseTravers {

        @Override
        protected void doTravers(TreeNode node) {
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.add(node);
            while (!queue.isEmpty()) {
                TreeNode treeNode = queue.pop();
                visitNode(treeNode);
                if (treeNode.left != null) {
                    queue.add(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.add(treeNode.right);
                }
            }
        }
    }

    //============================================
    public static abstract class BaseTravers {
        private StringBuilder sbuilder;
        public String getName() {
            return getClass().getSimpleName();
        }
        public void travers(TreeNode node) {
            sbuilder = new StringBuilder();
            sbuilder.append(String.format("%1$-30s", getName() + ":"));
            sbuilder.append("[ ");
            if (node == null) {
                sbuilder.append(" ]");
                System.out.println(sbuilder);
                return;
            }
            doTravers(node);
            String rest = sbuilder.substring(0, sbuilder.length() - 2) + " ]";
            System.out.println(rest);
        }

        abstract protected void doTravers(TreeNode node);

        protected void visitNode(TreeNode node) {
            if (node == null) {
                return;
            }
            sbuilder.append(node.toString());
            sbuilder.append(", ");
        }
    }
}
